package dcutils.graphs;

import java.util.*;

/**
 * An implementation of the unweighted graph data structure.<br/>
 * Instances of this class contain adjacency lists of vertices and edges.<br/>
 * @author dca
 */
public class UnweightedGraph<V> extends Graph<V> {
   /**
    * The map of vertices to their respective adjacency lists (which is a set of vertices.)
    */
   private TreeMap<V, TreeSet<V>> adj;

   /**
    * Constructs an undirected graph by default.
    */
   public UnweightedGraph() {
      this(false);
   } // END constructor

   /**
    * Constructs a graph, either directed or undirected.
    * @param directed if true, the graph will be a directed graph, if false, it will not be directed.
    */
   public UnweightedGraph(boolean directed) {
      this.directed = directed;
      this.adj = new TreeMap<>();
   } // END constructor

   /**
    * Adds a vertex to the graph.<br />
    * This vertex will not currently have edges going to or from it.
    * @param vertex The vertex to add to the graph.
    */
   @Override
   public void addVertex(V vertex) {
      if(!hasVertex(vertex)) {
         adj.put(vertex, new TreeSet<V>());
      } // END if
   } // END addVertex

   /**
    * Checks if a vertex is within the graph.
    * @param vertex The vertex to check.
    * @return true or false.
    */
   @Override
   public boolean hasVertex(V vertex) {
      return adj.containsKey(vertex);
   } // END hasVertex

   /**
    * Adds an edge between vertices.<br />
    * If either of these vertices do not exist in the graph, nothing happens.<br />
    * If the graph is undirected, the edge will be add not only from->to, but also to->from.
    * @param from The vertex the edge begins.
    * @param to The vertex the edge will end.
    */
   public void addEdge(V from, V to) {
      if(hasVertex(from) && hasVertex(to)) {
         adj.get(from).add(to);
         if(!directed) adj.get(to).add(from);
      } // END if
   } // END addEdge

   /**
    * Checks if an edge is within the graph.
    * @param from The vertex the edge begins.
    * @param to The vertex the edge ends.
    * @return true or false.
    */
   public boolean hasEdge(V from, V to) {
      return (
         hasVertex(from) && hasVertex(to) ?
         adj.get(from).contains(to) :
         false
      );
   } // END hasEdge

   /**
    * Returns an array of vertices from within the graph, no edges.
    * @return String A string array of vertices.
    */
   @Override
   public String verticesToString() {
      return adj.keySet().toString();
   } // END verticesToString

   /**
    * Returns the list of edges for a given vertex, as a string.
    * @param vertex The vertex from which the edges must begin.
    * @return String A string array of edges, preceded by the vertex.
    */
   @Override
   public String edgesToString(V vertex) {
      return (
         null == vertex ?
         "" :
         String.format(
            "%s -> %s",
            vertex,
            adj.get(vertex)
         )
      );
   } // END edgesToString

   /**
    * Returns all vertices and edges in the entire graph.
    * @return String A string array of vertices and their edges.
    */
   @Override
   public String graphToString() {
      final StringBuffer buffer = new StringBuffer(adj.keySet().size() * 1024);

      boolean first = true;
      for(V vertex : adj.keySet()) {
         if(!first) buffer.append(String.format("%n"));
         buffer.append(edgesToString(vertex));
         first = false;
      } // END loop

      return buffer.toString();
   } // END graphToString

   /**
    * Clears out the graph.
    */
   @Override
   public void clearGraph() {
      adj.clear();
   } // END clearGraph
} // END class UnweightedGraph
